#include "main/utils.h"
using namespace std;

struct PrefixNode {
  bool terminal = false;
  PrefixNode* childern[26];
};

void insert(PrefixNode* root, const string& word) {
  auto node = root;
  for (auto ch : word) {
    if (node->childern[ch - 'a'] == nullptr) {
      node->childern[ch - 'a'] = new PrefixNode();
    }
    node = node->childern[ch - 'a'];
  }
  node->terminal = true;
}

PrefixNode* buildPrefix(const vector<string>& dict) {
  PrefixNode* root = new PrefixNode();
  for (auto word : dict) {
    insert(root, word);
  }
  return root;
}

bool dfs(PrefixNode* node, const string& target, int index, int modify_num) {
  if (!node) {
    return false;
  }
  if (node->terminal && index == target.size() && modify_num == 1) {
    return true;
  }
  if (index < target.size() && modify_num <= 1) {
    bool found = false;
    for (int i = 0; i < 26 && !found; ++i) {
      int new_modify_num = (i == target[index] - 'a') ? modify_num : modify_num + 1;
      found = dfs(node->childern[i], target, index + 1, new_modify_num);
    }
    return found;
  }
  return false;
}

bool search(const vector<string>& dict, const string& target) {
  PrefixNode* prefix_tree_node = buildPrefix(dict);
  return dfs(prefix_tree_node, target, 0, 0);
}

int main() {
  vector<string> dict = {"happy", "new", "year"};
  cout << search(dict, "now") << endl;
  cout << search(dict, "new") << endl;
  cout << search(dict, "happy") << endl;
  cout << search(dict, "happo") << endl;
  cout << search(dict, "yaer") << endl;

  return 0;
}
